題目

2028. Find Missing Observations
難度: 中等但異常簡單

題意

有m+n個六面骰子，給定長度m的整數陣列rolls，代表前m個骰子的分布；給定mean代表m+n個骰子的平均值；給定整數n代表有n個骰子不確定的骰子。
求一個滿足要求的整數陣列，代表n個骰子的分布；若無法滿足則回傳空陣列。

方向

這題真的是medium程度嗎XD
題目還詳細說明平均值(mean)的定義: 算術平均數是一組樣本的和除以樣本的數量

首先累加m個骰子的總和，再計算全部骰子的總和(m+n) * mean
接著可得知剩餘骰子之總和為全部骰子之總和-m個骰子之總和

檢查是否有解，若剩餘骰子全部骰到6還滿足不了剩餘點數，或剩餘骰子全部骰到1仍超出剩餘點數，則不可能有解。

因為題目只要求一種滿足要求的解，因此怎麼分配點數就看個人發揮。
我的做法是n個骰子都先分配1點數，再將剩餘的點數依序塞爆，直到沒有剩餘的點數。

實作

class Solution
{
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n)
    {
        int         m           = (int) rolls.size();
        int         rolls_sum   = accumulate(rolls.begin(), rolls.end(), 0);
        int         total_sum   = mean * (m + n);
        int         missing_sum = total_sum - rolls_sum;
        
        vector<int> res;
        if (missing_sum > 6 * n || missing_sum < n)
            return res;

        missing_sum -= n;
        res = vector<int>(n, 1);
        int idx = 0;
        while (missing_sum)
        {
            if (missing_sum >= 5)
            {
                res[idx] = 6;
                missing_sum -= 5;
                idx++;
            }
            else
            {
                res[idx] += missing_sum;
                missing_sum -= missing_sum;
                idx++;
            }
        }
        return res;
    }
};

分析

時間複雜度: O(M+N)，累加M長度陣列的總和，再建立N長度的陣列
空間複雜度: O(1)，除了回傳的陣列之外無額外需求

結果